package com.jwetherell.algorithms.search;

public class InterpolationSearch {

    private static int[] sortedData = null;

    // Assuming the array is sorted
    public static final int find(int value, int[] array) {
        InterpolationSearch.sortedData = array;
        try {
            return recursiveFind(value, 0, InterpolationSearch.sortedData.length - 1);
        } finally {
            InterpolationSearch.sortedData = null;
        }
    }

    private static int recursiveFind(int value, int start, int end) {
        if (start == end) {
            if (value == sortedData[start])
                return start; // start==end
            return Integer.MAX_VALUE;
        }

        int mid = start + ((value - sortedData[start]) * (end - start)) / (sortedData[end] - sortedData[start]);
        if (mid < 0 || mid > end)
            return Integer.MAX_VALUE;
        int midValue = sortedData[mid];
        if (value == midValue)
            return mid;
        if (value > midValue) {
            return recursiveFind(value, mid + 1, end);
        } else {
            return recursiveFind(value, start, mid - 1);
        }
    }

    public static void main(String[] args) {
    	sortedData = new int [] {2,3,4,5,6,7,8};
    	
		int index = recursiveFind(7, 0, 6);
		System.out.println("Index: " + index);
		System.out.println("Value: " + sortedData[index]);
	}
    
}
